﻿//给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
//两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空
//子字符串：
//s = s1 + s2 + ... + sn
//t = t1 + t2 + ... + tm
//| n - m| <= 1
//交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
//注意：a + b 意味着字符串 a 和 b 连接。
//
//输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
//输出：true
//
//输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
//输出：false
//
//输入：s1 = "", s2 = "", s3 = ""
//输出：true
//
//提示：
//	0 <= s1.length, s2.length <= 100
//	0 <= s3.length <= 200
//	s1、s2、和 s3 都由小写英文字母组成

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        // 1.创建dp表
        // 2.初始化
        // 3.填表
        // 4.返回值
        int m = s1.size(), n = s2.size();
        if (m + n != s3.size())
            return false;
        s1 = " " + s1, s2 = " " + s2, s3 = " " + s3;
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) // 初始化第⼀⾏

            if (s2[j] == s3[j])
                dp[0][j] = true;
            else
                break;
        for (int i = 1; i <= m; i++) // 初始化第⼀列

            if (s1[i] == s3[i])
                dp[i][0] = true;
            else
                break;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j]) ||
                (s2[j] == s3[i + j] && dp[i][j - 1]);
        return dp[m][n];
    }
};